{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from itertools import combinations, product\n",
    "from collections import defaultdict"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def sum4(data):\n",
    "    # store 2-sums\n",
    "    sum_of_2 = defaultdict(list)\n",
    "    for i, j in combinations(range(len(data)), 2):\n",
    "        k = data[i] + data[j]\n",
    "        sum_of_2[k].append((i, j))\n",
    "\n",
    "    # match pairs of 2-sums\n",
    "    sum_of_4 = set()\n",
    "    for k in sum_of_2:\n",
    "        if k >= 0 and -k in sum_of_2:\n",
    "            for i, j in product(sum_of_2[k], sum_of_2[-k]):\n",
    "                index = tuple(sorted(set(i + j)))\n",
    "                if len(index) == 4:\n",
    "                    sum_of_4.add(index)\n",
    "\n",
    "    return sum_of_4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## run"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([  5,   1,  -9,  -6,   4,  -4,   7,   1, -10,  -6])"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n = 10\n",
    "data = np.random.randint(-n, n, n)\n",
    "data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(0, 1, 4, 8) [  5   1   4 -10]\n",
      "(1, 2, 6, 7) [ 1 -9  7  1]\n",
      "(1, 3, 4, 7) [ 1 -6  4  1]\n",
      "(0, 3, 6, 9) [ 5 -6  7 -6]\n",
      "(0, 4, 7, 8) [  5   4   1 -10]\n",
      "(1, 4, 7, 9) [ 1  4  1 -6]\n"
     ]
    }
   ],
   "source": [
    "for index in sum4(data):\n",
    "    print(index, data[list(index)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
